package me.eg.first;

import java.util.Stack;

/**
 * 85. 最大矩形
 *
 * https://leetcode-cn.com/problems/maximal-rectangle/
 */
public class MaximalRectangle {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;

        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] heightSum = new int[rows][cols];
        for (int c = 0; c < cols; c++) {
            for (int r = 0; r < rows; r++) {
                if (matrix[r][c] == '1') {
                    if (r == 0) heightSum[r][c] = 1;
                    else heightSum[r][c] = heightSum[r - 1][c] + 1;
                }
            }
        }

        int maxArea = 0;
        for (int r = 0; r < rows; r++) {
            int maxAreaInRow = largestRectangleArea(heightSum[r]);
            if (maxAreaInRow > maxArea) maxArea = maxAreaInRow;
        }
        return maxArea;
    }

    private int largestRectangleArea(int[] heights) {
        Stack<Integer> heightStack = new Stack<>();
        Stack<Integer> widthStack = new Stack<>();

        int maxArea = 0;
        for (int i = 0; i <= heights.length; i++) {
            int accWidth = 0;
            int height = 0;
            if (i != heights.length) height = heights[i];

            while (!heightStack.isEmpty() && heightStack.peek() >= height) {
                int tempHeight = heightStack.pop();
                accWidth += widthStack.pop();

                int tempArea = tempHeight * accWidth;
                if (tempArea > maxArea) maxArea = tempArea;
            }
            heightStack.push(height);
            widthStack.push(accWidth + 1);
        }
        return maxArea;
    }
}
